package 记忆化搜索;

import java.util.Arrays;

// 零钱兑换1
public class Solution8 {
    public int coinChange(int[] coins, int amount) {
        mem = new int[amount + 1];
        Arrays.fill(mem, -1);
        int ans = dfs(amount, coins);
        return ans == 100010 ? -1 : ans;
    }

    int[] mem;

    private int dfs(int rest, int[] coins) {
        if (rest == 0) return 0;
        if (mem[rest] != -1) return mem[rest];
        int ans = 100010;
        for (int coin : coins) {
            if (rest >= coin) ans = Math.min(ans, dfs(rest - coin, coins) + 1);
        }
        mem[rest] = ans;
        return ans;
    }
}